package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月12日
*时间：下午6:47:39
*/
public class Q165 {

    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode c1 = null, c2 = null;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                if (c1 == null) {
                    c1 = l2;
                } else if (c2 == null) {
                    c2 = l2;
                    c1.next = c2;
                } else {
                    c2.next = l2;
                    c2 = c2.next;
                }
                l2 = l2.next;
            } else {
                if (c1 == null) {
                    c1 = l1;
                } else if (c2 == null) {
                    c2 = l1;
                    c1.next = c2;
                } else {
                    c2.next = l1;
                    c2 = c2.next;
                }
                l1 = l1.next;
            }
        }
        while (l1 != null) {
            c2.next = l1;
            c2 = c2.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            c2.next = l2;
            c2 = c2.next;
            l2 = l2.next;
        }
        return c1;
    }

    @Test
    public void testA() {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(2);
        ListNode c = mergeTwoLists(l1, l2);
        System.out.println(c);
    }
}
